class Solution {
    //因为是归并排序，这里要对两个数组进行排序
    //设置一个全局变量
    int[] tmp;

    public int reversePairs(int[] nums) {
        //设置一个函数处理这个问题
        int n = nums.length;
        tmp = new int[n];
        //返回归并排序的结果
        return mergeSort(nums, 0, n - 1);
    }

    /**
     * 进行归并排序
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public int mergeSort(int[] nums, int left, int right) {


        //处理边界情况，这时是绝对没有逆序对的
        if (left >= right) {
            return 0;
        }
        int ret = 0;

        /**
         * 按照归并排序的主逻辑,先选择一个中间点，对数组进行划分
         * 数组划分为两部分：[left,mid] [mid + 1,right]
         */
        int mid = (left + right) / 2;
        //处理左区域 + 排序 右区域 + 排序
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        //处理一左一右的个数
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        //处理排序
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }

        return ret;
    }
}

public class Test01 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 1, 2, 1};
        Solution solution = new Solution();
        System.out.println(solution.reversePairs(arr));
    }
}
